package leetcode.L1000;

import java.util.HashMap;
import java.util.Map;

public class Ex523 {
    //同余定理。
    //(s[i]-s[j])%k=0可以得出 s[i]%k=s[j]%k
    //只要得到相同的余数，就可以判断
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        int [] s = new int[nums.length+1];
        for(int i = 1;i<=nums.length;i++){
            s[i] = nums[i-1]+s[i-1];
        }
        for(int i = 0;i<s.length;i++){
            int t = s[i]%k;
            if(map.containsKey(t)){
                int ind = map.get(t);
                if(i-ind>=2){
                    return true;
                }
            }else{
                map.put(t,i);
            }
        }
        return false;
    }
}
